# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        flags = [0 for _ in range(cols * rows)]
        for i in range(rows):
            for j in range(cols):
                if self.find_path(matrix, i, j, rows, cols, path, flags):
                    return True
        return False
    def find_path(self, matrix, i, j, rows, cols, path, flags):
        if not path:
            return True
        if -1 < i < rows and -1 < j < cols and matrix[i * cols + j] == path[0] and not flags[i * cols + j]:
            flags[i * cols + j] = 1
            if(self.find_path(matrix, i+1, j, rows, cols, path[1:], flags) or
                self.find_path(matrix, i-1, j, rows, cols, path[1:], flags) or
                self.find_path(matrix, i, j+1, rows, cols, path[1:], flags) or
                self.find_path(matrix, i, j-1, rows, cols, path[1:], flags)):
                return True
            flags[i * cols + j] = 0
        return False




        
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        assistMatrix = [True]*rows*cols# 用该矩阵防止找回去
        for i in range(rows):
            for j in range(cols):
                if(self.hasPathAtAStartPoint(matrix,rows,cols, i, j, path, assistMatrix)):
                    return True
        return False

    def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, assistMatrix):
        if not path:
            return True
        index = i*cols+j
        if i<0 or i>=rows or j<0 or j>=cols or matrix[index]!=path[0] or assistMatrix[index]==False:
            return False
        assistMatrix[index] = False
        if(self.hasPathAtAStartPoint(matrix,rows,cols,i+1,j,path[1:],assistMatrix) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i-1,j,path[1:],assistMatrix) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i,j-1,path[1:],assistMatrix) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i,j+1,path[1:],assistMatrix)):
            return True
        assistMatrix[index] = True
        return False